/*
 *https://leetcode.cn/problems/most-stones-removed-with-same-row-or-column/
 *947. 移除最多的同行或同列石头
 *medium 吴朝泽 2024.9.27
 *并查集
 如果两个点在同一行或同一列上，归为同一个连通组。给出(0, 0), (0, 1), (1, 0), (1, 1), (2, 2) 五个石子
 石子 (0, 0), (0, 1), (1, 0), 和 (1, 1) 形成一个连通组，而石子 (2, 2) 是单独的一个组。
 即有两个连通组。通过画图可知移除最多可以是三个石子：5 - 2 = 3 。
 最终返回 n - uf.group_count() 即可。
*/

class union_find
{
    vector<int> parent;
    int group;
public:

    // 构造从 0 到 n - 1 的节点
    union_find(int n) :
        parent(n), group()
    {
        for (int i = 0; i < n; ++i)
        {
            parent[i] = i;
        }
        group = n;
    }

    // 合并两个节点
    void pair(int index1, int index2)
    {
        int root_1 = find(index1), root_2 = find(index2);
        if (root_1 != root_2)
        {
            --group;
        }
        parent[root_2] = root_1;
    }

    // 找到根节点
    int find(int index)
    {
        vector<int> temp;

        int root = index;
        for (; parent[root] != root; root = parent[root])
        {
            temp.emplace_back(root);
        }

        for (auto& it : temp)
        {
            parent[it] = root;
        }
        
        return root;
    }

    // 判断连接性
    bool check(int index1, int index2)
    {
        return find(index1) == find(index2);
    }

    // 返回连通图的数量
    int group_count()
    {
        return group;
    }
};

class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        int n = stones.size();
        union_find uf(n);
        for(int i = 0; i < n; ++i)
        {
            for(int j = i + 1; j < n; ++j)
            {
                //将在同一行或同一列的石子合并起来，归为一个连通组
                if(stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1])
                    uf.pair(i, j);
            }
        }
        return n - uf.group_count();
    }
};